package com.zp.self.module.level_4_算法练习.数据结构.数组;

/**
 * @author By ZengPeng
 */
public class 力扣_414_第三大的数 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_414_第三大的数().thirdMax(new int[]{3, 2, 1}));
        System.out.println(new 力扣_414_第三大的数().thirdMax(new int[]{1,2}));
        System.out.println(new 力扣_414_第三大的数().thirdMax(new int[]{2, 2, 3, 1}));
    }

    /**
     * 题目：给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
     * 进阶：你能设计一个时间复杂度 O(n) 的解
     *
     * 示例 1：
     * 输入：[3, 2, 1]
     * 输出：1
     * 解释：第三大的数是 1 。
     *
     * 示例 2：
     * 输入：[1, 2]
     * 输出：2
     * 解释：第三大的数不存在, 所以返回最大的数 2 。
     *
     * 分析：
     *      1.先排序 ，然后再判断
     *      2.进阶：定义3个变量
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public int thirdMax(int[] nums) {
        //方案2：定义3个变量
        Integer first = null, second = null, third = null;
        for(int i = 0; i < nums.length; i++) {
            Integer cur = nums[i];
            if(cur.equals(first) || cur.equals(second) || cur.equals(third)) continue;
            if(first == null || cur > first) {
                third = second;
                second = first;
                first = cur;
            } else if(second == null || cur > second) {
                third = second;
                second = cur;
            } else if(third == null || cur > third) {
                third = cur;
            }
        }
        return third == null ? first : third;

        //方案1：排序后比较
//        int length = nums.length;
//        Arrays.sort(nums);
//        int mingci = 1,pro=nums[length-1] ;
//        for (int i = length-2; i>=0; i--) {
//            if(pro == nums[i])continue;
//            if(++mingci==3) return nums[i];
//            pro=nums[i];
//        }
//        return nums[length-1];
    }
}
